package zuo.baseUP3_Manacher_;

/**
 * @Author: Forx
 * @Data: 2021/6/18
 * @Desc: Algorithm - zuo.baseUP3_Manacher_
 * @Version: v1.0
 */

import java.util.ArrayList;
import java.util.LinkedList;

/**
 * Manacher算法解决的问题
 * 字符串str中,最长回文子串的长度如何求解?
 * 如何做到时间复杂度0(N)完成?
 *
 * 如字符串"1 2 2 1 3 1 2 2 1'
 * 经典解法
 * 以每个字符为轴向两边扩展,直到两边不相等,但是这种解法解决不了1 2 2 1这种回文串
 * 优化:在每个字符中间填充一个字符 _ 1 _ 2 _ 2 _ 1 _ 3 _ 1 _ 2 _ 2 _ 1 _
 * 然后再以每个字符为轴扩充 这样就能解决 1 2 2 1这种问题了
 * 最后再除以2 并且添加的字符加什么都行,因为总是虚字符和虚字符,实字符和实字符比
 * 时间复杂度是O(n^2)
 *
 * Manacher算法 O(n)
 * 我们首先用一个数组pArr来保存遍历过的每一个字符的最大回文半径
 * 一个变量R来保存遍历过的最大回文半径的右边界
 * C来保存出现R时的中心位置
 * 如 _ 1 _ 2 _ 2 _ 1 _ 3 _ 1 _ 2 _ 2 _ 1 _
 * i: 0 1 2 3 4 5 6 7 8 9 101112131415161718
 * 当i走到4的时候R是8 C是4 pArr = [... 4 ...]
 * 遍历新的i有一下三种情况
 * 情况1. i 不在R内 此时还用经典方法解决,并且R,C一定会更新
 * 情况2. i 在R内,此时我们通过C,R可以找到出一个回文区域[... L .i'. C .i. R ...]
 *          我们可以通过i找到i',然后通过pArr[i']找到以i'为中心的回文区域,该回文区域
 *          有三种情况:
 *          1.回文区域完全在L-C内 则易知i的回文区域也在C-R内,此时直接更新pArr[i]
 *          2.回文区域部分在L-C内 我们将i'的回文区域即 [..i'L ... L ... i' ...i'R ... R ...]
 *            此时我们知道L-i'-i'+len(i'-L)必然也是一个回文区域,并将i'+len(i'-L)简写成i'L'
 *            又因为i'L'是在C的回文区域内,则str[C + len(C-i'L')] == str[i'L'],我们知道
 *            str[L-1] == str[i'L'+1] == str[C + len(C-i'L')-1]  且 str[L-1] != str[R+1],
 *            因此str[C + len(C-i'L') - 1] != str[R+1] 故i的回文半径就是R-i;
 *          3.回文区域压线 这种情况只能在R外继续经典方法
 *
 *
 *
 * */
public class Main {
    public static char[] fillStr(char[] str){
        char[] res = new char[str.length*2+1];
        int index = 0;
        for (int i = 0; i < res.length; i++) {
            res[i] = (i & 1) == 0 ? '#' : str[index++];//i&1==0为偶数位
        }
        return res;
    }
    public static int manacher(char[] str){
        int[] pArr = new int[str.length];
        int R = -1;//这个R是上面注释中R+1即是终止位置,为了方便做了改动
        int C = -1;
        int maxLen = Integer.MIN_VALUE;
        for (int i = 0; i < str.length; i++) {
            pArr[i] = R>i?Math.min(pArr[2*C-i],R-i):1;//C-(i-C) = 2*C-i = C<<1 - i
            while (i+pArr[i] < str.length && i - pArr[i] > -1){
                if(str[i+ pArr[i]] == str[i - pArr[i]]){
                    pArr[i]++;
                }else {
                    break;
                }
            }
            if(i+pArr[i]>R){
                R = i+pArr[i];
                C = i;
            }
            maxLen = Math.max(R,pArr[i]);
        }
        return maxLen-1;//maxLen = 2*(maxR/2) -1;
    }

    /**
     * 由一个代表题目,引出一种结构
     * 【题目】
     * 有一个整型数组arr和一个大小为w的窗口从数组的最左边滑到最右边,窗口每次向右边滑
     * 一个位置。
     * 例如,数组为[4,3,5,4,3,3,6,7],窗口大小为3时
     * [435]4336
     * 4[354]3367
     * 43[543]367
     * 435[433]67
     * 4354[336]7
     * 43543[367]
     * 窗口中最大值为5窗口中最大值为5窗口中最大值为5窗口中最大值为4窗口中最大值为6
     * 窗口中最大值为7
     * 如果数组长度为n,窗口大小为w,则一共产生n-w+1个窗口的最大值。
     * 请实现一个函数。输入:整型数组arr,窗口大小为w。
     * 输出:一个长度为n-w+1的数组res,res[i]表示每一种窗口状态下的以本题为例,结果应该
     * 返回{5,5,5,4,6,7}。
     *
     * 看看最值索引是不是在新的窗口内,如果在则只和新数比
     *
     * 双端队列  [大-小]
     * R往右动时:新入的数,如果大于等于尾部的数则从尾部弹出,直到准备假如的数小于尾部的数据,如果小于则从尾部进,另外我们进的是数据的索引
     * L往右动时:假如过期的数据是头部的数据,那就弹出,如果不是就不管
     *
     * 原理:
     *  在R移动时我们实际维持的是按照过期顺序排列的从大到小的值,如果有一个值比里面的值大,但是过期晚,那就代表里面的值没有机会成为最大值
     *  故在加入这个最大值得时候会将前面的都弹出
     * */

    public static int[] getWindowMax(int[] data,int wid){
        LinkedList<Integer> qmax = new LinkedList<>();

        int[] ans = new int[data.length-wid+1];

        int index = 0;
        for (int i = 0; i < data.length; i++) {
            while (!qmax.isEmpty() && data[qmax.peekLast()] <= data[i]){
                qmax.pollLast();
            }
            qmax.addLast(i);
            if(qmax.peekFirst() == i-wid){
                qmax.pollFirst();
            }
            if(i > wid-1){
                ans[index++] = data[qmax.peekFirst()];
            }
        }

        return ans;
    }

    /**
     *
     * 背景:
     *      如何找到一个数组中每个数左边最近比他小的数和右边最近比他大的数
     * 经典解法:暴力 时间复杂度是O(n^2)
     * 优秀解法:利用单调栈
     * 单调栈
     * |          |  小
     * |          |
     * |__[...]___|  大
     * 如果入栈的时候发现栈顶元素比自己小,则栈顶元素退栈,并生成栈顶元素的信息即当前栈顶右边最近比他的数就是准备入栈的元素,左边最小就是次栈顶链表
     * 末尾的元素,一直退到栈顶元素大于等于入栈元素则停止出栈
     *
     * 单调栈的应用
     * 定义:数组中累积和与最小值的乘积,假设叫做指标A。
     * 给定一个数组,请返回子数组中,指标A最大的值。
     * 遍历每一个元素,找到以这个元素为最小值且包含元素最多的子数组得到指标A放入存储A的数组中
     * "找到以这个元素为最小值且包含元素最多的子数组"这个即利用的就是单调栈
     *
     * */
    public static int[][] getLRbuff(int[] data){
        return null;

    }




}
